class Solution9112MergeSort {
     int[] ret ; // 把临时数组定义到外面作为公共数组, 这样来减少创建数组的开销
    public int[] sortArray(int[] nums) {
          ret = new int[nums.length] ;    // 创建临时数组 ;
        mergeSort(nums , 0 , nums.length-1) ;
        return nums ;
    }
    private void mergeSort(int[] nums , int left , int right){
        if(left >= right) return ;
       // 找一个中间点
       int mid = left + (right-left)/2 ;
       // 根据中间点划分数组 ;[0,mid] , [mid+1 ,len];
       // 递归两个区间
       mergeSort(nums , left , mid) ; 
       mergeSort(nums , mid+1 , right) ; 
       // 两个区间有序后 , 合并两个区间 ;
       // 有一个临时数组,来辅助合并
       int l = left , r = mid+1 , i = 0 ;
       while(l <= mid && r <= right){   //双指针, 对比,哪个小就放到临时数组里
          ret[i++] = nums[l] <= nums[r] ? nums[l++]:nums[r++] ; 
       }
       // 最后l 或r 有一个可能没有遍历完 ;
       while(l <= mid){
         ret[i++] = nums[l++] ; 
       }
       while(r <= right){
         ret[i++] = nums[r++] ;
       }
        // 把临时数组里排序好的元素,写回到原来的数组里
        for(int j=left ; j <= right ; j ++){
            nums[j] = ret[j-left] ;
        }
    }

}